#include <limits.h>   // INT_MAX, 
// #include <limits>     // std::numeric_limit<int>::max()
#include <vector>
#include <iostream>
#include <algorithm>   //  min,
#include <stdio.h>
#include <queue>
#include <map>
#include <utility>
// #include <bits/stdc++.h>  


// 算法教程： https://www.bilibili.com/video/BV1Eb41177d1/?spm_id_from=333.337.search-card.all.click
typedef std::pair<int, int> pii;                // (节点, 权重)
typedef std::vector<std::vector<pii>> AdjList;  // AdjList邻接表;
typedef std::vector<std::vector<int>> Matrix;


AdjList edges = {{{1,4}, {7,8}},              // node0
                {{2,8}, {7,11}},              // node1
                {{1,8},{3,7},{8,2}},          // node2
                {{2,7},{4,9},{5,14}},         // node3
                {{3,9},{5,10}},               // node4
                {{6,2},{2,4},{3,14},{4,10}},  // node5
                {{7,1},{8,6},{5,2}},          // node6
                {{0,8},{1,11},{8,7},{6,1}},   // node7
                {{2,2},{7,7},{6,6}},          // node8   row num  ==> src node idx
                };

// Prim(普里姆)最小生成树算法

/**
 * @brief 最小生成树
 * 
 *  1. 树的要求：
 *      - 无环7,7,vector<std::vector<pii>> AdjList;  // AdjList邻接表;
typedef std::vector<std::vector<int>> Matrix;


/**
 * @brief  prim算法思路和步骤
 * 
 * @step   
 *   1. 将所有顶点分类两个集合： 1个是已经确定连接方式的顶点集合(selected)， 另一类是还没有确定连接方式的顶点集合(unselected);
 *         - std::vector<bool> selected(n, false);       // true和false则构成了两个集合
 *   2. std::vector<int>  min_dists(n, MAX_INT);  
 *   3. std::vector7,
 * @return int 
 */
int prim(const AdjList& graph) {
    int node_num = graph.size();     // node number
    int dist = 0;                    // tolal distance of min spaning tree

    // 使用优先队列（最小堆）来存储边，按边权从小到大排列
    std::priority_queue<pii, std::vector<pii>, std::greater<pii>> pq;

    // 标记数组，用于记录某个顶点是否已经在最小生成树中graph) {
    int node_num = graph.size();     // node number
    int dist = 0;                    // tolal distance of min spaning tree

    // 使用优先队列（最小堆）来存储边，按边权从小到大排列
    std::priority_queue<pii, std::vector<pii>, std::greater<pii>> pq;

    // 标记数组，用于记录某个顶点是否已经在最小生成树中
    std::vector<bool> inMST(node_num, false);

    // 任选一个顶点作为起始点，这里选择第一个顶点，权值为0
    std::vector<bool> inMST(node_num, false);

    // 任选一个顶点作为起始点，这里选择第一个顶点，权值为0
    pq.push(std::make_pair(0, 0));

    while (!pq.empty()) {            // TODO: ?????
        int u = pq.top().second;     // 获取当前边的目标顶点
        int w = pq.top().first;      // 获取当前边的权值
        pq.pop();

        if (inMST[u])                // 如果当前顶点已经在最小生成树中，则跳过
            continue;

        inMST[u] = true;            // 累加当前边的权值

        // 遍历当前顶点的邻居
        for (const auto& neighbor : graph[u]) {
            int v = neighbor.first; // 邻居的顶点编号
            int weight = neighbor.second; // 边的权值

            // 如果邻居不在最小生成树中且边权小于当前已知的最小权值，则将该边加入优先队列
            if (inMST[v] == false) {
                pq.push(std::make_pair(weight, v));
            }
        }
    }

    return dist; // 返回最小生成树的总权值
}

// int prim(const AdjList& graph) {
//     int dist  = 0;
//     int nnode = graph.size();
//     std::vector<bool> isAdded(nnode, false);
//     int node_count = 0;

//     isAdded[0] = true;
//     node_count++;

//     // 
//     // std::map<std::pair<int,int> /*<src_node, dst_node>*/, int /*weight*/ >  edge_dists;
//     std::vector<std::pair<std::pair<int,int>, int>>  edge_dists;

//     std::vector<std::pair<int, int>> edgeAdded;

//     int src = 0;     
//     for (auto &ngbs : graph) {      // 
//         for (auto& pr : ngbs)
//         {
//             int dst = pr.first;
//             int val = pr.second;  

//             if (dst > src) {
//                 continue;
//             }
//             // edge_dists.emplace(std::make_pair(std::make_pair(src, dst), val));
//             edge_dists.push_back(std::make_pair(std::make_pair(src, dst), val));
//         }
//         src++;
//     }


//     while (node_count < nnode)   
//     {
//         std::pair<int, int> min_edge{0, 0};
//         int min_dist      = INT_MAX;
//         for (auto &pr : edge_dists) {    
//             int s   = pr.first.first;
//             int d   = pr.first.second;
//             int val = pr.second;

//             if ((isAdded[s] == 1 && isAdded[d] == 0) || (isAdded[s] == 0 && isAdded[d] == 1)) {
//                 if (val < min_dist) {
//                     min_edge.first  = std::min(s,d);
//                     min_edge.second = std::max(s,d);

//                     min_dist = val;
//                 }
//             }
//         }

//         if (isAdded[min_edge.first] == true) {
//             isAdded[min_edge.second] = true;
//         } else {
//             isAdded[min_edge.first] = true;
//         }
//         node_count++;
//         edgeAdded.push_back(min_edge);
//     }
    

//     // 
//     for (auto& eg : edgeAdded) {
//         for (auto& nr : edge_dists)
//         {
//             // {{src, dst}, dist}
//            if (eg == nr.first) {
//                dist +=  nr.second;
//            }
//         }
        
//     }


//     return dist;
// }  




int main(int argc, char* argv[]) {
    int dist = prim(edges);
    std::cout << "Total weight of MST: " << dist << std::endl;
    return 0;
}